Inverse-free Berlekamp-Massey-Sakata Algorithm and Small Decoders for Algebraic-Geometric Codes

摘要

This paper proposes a novel algorithm for finding error-locators ofalgebraic-geometric codes that can eliminate the division-calculations offinite fields from the Berlekamp-Massey-Sakata algorithm. This inverse-freealgorithm provides full performance in correcting a certain class of errors,generic errors, which includes most errors, and can decode codes on algebraiccurves without the determination of unknown syndromes. Moreover, we proposethree different kinds of architectures that our algorithm can be applied to,and we represent the control operation of shift-registers and switches at eachclock-timing with numerical simulations. We estimate the performance incomparison of the total running time and the numbers of multipliers andshift-registers in three architectures with those of the conventional ones forcodes on algebraic curves.